Mit Hilfe des \textbf{Diffie-Hellman-Verfahrens} können geheime Schlüssel über unsichere Leitungen übertragen werden.
Es bildet die Grundlage für das ElGamal-Verfahren, wobei es kein Public-Key-Verfahren ist.

Man geht davon aus, dass zwei Personen ein symmetrisches Verschlüsselungsverfahren zur Kommunikation nutzen. Sie sind über eine unsichere Leitung verbunden und haben bisher keinen gemeinsamen Schlüssel ausgetauscht. Durch Nutzung des Diffie-Hellman-Verfahrens können sie über diese Leitung einen geheimen Schlüssel vereinbaren, den ein möglicher Zuhörer nicht mitbekommt.

Statt dem Faktorisierungsproblem beruht das Diffie-Hellman-Verfahren auf einem anderen zahlentheoretischen Problem: den diskreten Logarithmen.

\subsubsection{Diskrete Logarithmen}

Sei $p$ eine Primzahl und $\tmod p$ eine zyklische prime Restklassengruppe mit der Ordnung $p-1$. Bei der Zahl $g$ handelt es sich um eine Primitivwurzel $\tmod p$. Daher gibt es für jede Zahl $A$ einen Exponenten $a$, so dass folgendes gilt:

\begin{center}
$A\equiv g ^ a \tmod p$ mit $A\in\lbrace 1,2,...,p-1\rbrace$ und $a\in \lbrace0,1,2,...,p-2\rbrace$
\end{center}

Der Exponent $a$ heißt \textbf{diskreter Logarithmus} von $A$ zur Basis $g$. Man schreibt hierfür $ a = \log_{g}A$. 
Die Berechnung diskreter Algorithmen gilt als schwieriges Problem. Es sind derzeit keine effizienten Algorithmen zur Lösung dieses Problems bekannt.

\textbf{Beispiel}

Man wählt $p=13$. Eine Primitivwurzel $\tmod 13$ ist $2$. Zur Primitivwurzel $g=2$ wird nun die Wertetabelle der diskreten Exponentiation bestimmt. Dieser Vorgang ist die Umkehrfunktion des diskreten Logarithmus.

\begin{center}
\begin{tabular}{|c|c|}
\hline 
$2^a$ & $\equiv A \tmod 13$ \\
\hline
$2^0=1$ & 1 \\  
$2^1=2$ & 2 \\ 
$2^2=4$ & 4 \\ 
$2^3=8$ & 8 \\ 
$2^4=16$ & 3 \\ 
$2^5=32$ & 6 \\ 
$2^6=64$ & 12 \\
... & ... \\ 
$2^{11}=2048$ & 7 \\ 
\hline 
\end{tabular} 
\end{center}

In der nachfolgenden Tabelle sind die diskreten Logarithmen aller Elemente der Menge $\lbrace1,2,3...,12\rbrace$ zur Basis $2$ enthalten. Der zu $A$ gehörige Exponent $a$ kann aus der vorherigen Tabelle ermittelt werden.

\begin{center}
\begin{tabular}{|c|cccccccccccc|}
\hline 
A & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ 
\hline 
$log_{2}A$ & 0 & 1 & 4 & 2 & 9 & 5 & 11 & 3 & 8 & 10 & 7 & 6 \\ 
\hline 
\end{tabular} 
\end{center}

Es ist einfacher die diskrete Exponentiation zu berechnen als den diskreten Logarithmus zu ermitteln, weshalb dieses Verfahren als Einwegfunktion in der Kryptographie geeignet ist. 

Neben primen Restklassengruppen kann der diskrete Logarithmus auch in anderen zyklischen Gruppen definiert werden. Sei $G$ eine endliche zyklische Gruppe der Ordnung $n$ mit Erzeuger $g$ und sei $A$ ein Gruppenelement. Dann gibt es einen Exponenten $a\in\lbrace0,1,...,n-1\rbrace$ mit $A=g^a$. Dieser Exponent $a$ heißt diskreter Logarithmus von $A$ zur Basis $g$. 
Das Diffie-Hellman-Verfahren kann allen Gruppen G sicher implementiert werden, in denen die Berechnung diskreter Logarithmen schwer und die Ausführung der Gruppenoperatoren leicht ist.

Beispiel: die additiven Gruppe $\mathbb{Z}/n\mathbb{Z}$ (Addition als Gruppenoperation) für eine natürliche Zahl n. Sie ist zyklisch von der Ordnung n. Ein Erzeuger ist $1+n \mathbb{Z}$ (z.B. $n=4$ erzeugt Gruppe $\lbrace 1+0=1,1+1=2,1+2=3,4,5 \rbrace$).\\

Sei $A \in \lbrace 0,1,...,n-1\rbrace$. Der diskrete Logarithmus von $a$ von $A+n\mathbb{Z}$ zur Basis $1+n\mathbb{Z}$ ($a=log_{1+n\mathbb{Z}}A+n\mathbb{Z}$) genügt der Kongruenz
\begin{center} $A\equiv a \tmod n$. \end{center}

Also ist $A=a$. Die anderen Erzeuger von $\mathbb{Z}/n\mathbb{Z}$ sind die Restklassen $g+n\mathbb{Z}$ mit $\gcd(g,n)=1$. Der diskrete Logarithmus $a$ von $A+n\mathbb{Z}$ zur Basis $g+n\mathbb{Z}$ genügt der Kongruenz 
\begin{center} $A\equiv ga \tmod n$. \end{center}
 
Diese Kongruenz kann durch den erweiterten euklidischen Algorithmus gelöst werden. Folglich gibt es in dieser additiven Gruppe ($\mathbb{Z}/n\mathbb{Z}$) ein effizientes Verfahren zur Berechnung diskreter Logarithmen. Sie ist deshalb für die Implementierung des Diffie-Hellman-Verfahrens ungeeignet.

\subsubsection{Schlüsselaustausch}

Um einen Schlüssel vereinbaren zu können, müssen Alice und Bob eine Primitivwurzel $g \tmod p$ festlegen. Die beiden Zahlen $p$ und $g$ können öffentlich bekannt sein. Alice wählt eine beliebige, natürliche Zahl $a \in \lbrace0,1,...,p-2\rbrace $ und berechnet

\begin{center}
$A=g ^ a \tmod p$
\end{center}

Das Ergebnis $A$ sendet sie an Bob. Der verwendete Exponent $a$ bleibt geheim. Bob wählt ebenfalls eine beliebige, natürliche Zahl $b \in \lbrace0,1,...,p-2\rbrace$ und berechnet anschließend

\begin{center}
$B=g ^ b \tmod p$
\end{center}

Das Ergebnis sendet er an Alice. Der verwendete Exponent $b$ bleibt geheim. Um den geheimen Schlüssel zu berechnen, berechnet Alice

\begin{center}
$B^a \tmod p = g ^ {ab} \tmod p$
\end{center}

und Bob berechnet

\begin{center}
$A^b \tmod p = g ^{ab} \tmod p$
\end{center}

Der gemeinsame Schlüssel ist somit

\begin{center}
$K = g^{ab} \tmod p$.\\
\end{center}

Alice und Bob erhalten beide den selben Schlüssel, da $B^a \equiv g^{ab} \equiv A^b \tmod p$ gilt.

\textbf{Beispiel}

Alice und Bob vereinbaren $p=17$ und $g=3$. Anschließend wählt Alice den Exponenten $a=7$ und berechnet $A=g^a \tmod p = 11$. Das Ergebnis versendet sie an Bob. Dieser wählt den Exponenten $b=4$, berechnet $g^b \tmod p = 13$ und schickt $B$ an Alice. Für Alice ergibt sich der Schlüssel als $K=B^a \tmod p = 4$. Bob erhält den Schlüssel durch Berechnung von $K=A^b \tmod p = 4$. Der ausgetauschte Schlüssel ist folglich $K=4$.

\subsubsection{Diffie-Hellman-Problem}

Ein Angreifer erfährt die Zahlen $p,g,A $ und $B$. Um eventuell abgefangene Nachrichten entschlüsseln zu können, benötigt er die diskreten Logarithmen $a$ von $A$ und $b$ von $B$, mit deren Hilfe er den Schlüssel $K=g^{ab} \tmod p$ ermitteln kann. Das ist in bestimmten Gruppen nur mit enormem Rechenaufwand zu lösen. Dieses Problem wird als \textbf{Diffie-Hellman-Problem} bezeichnet.

Wer diskrete Logarithmen $\tmod p$ berechnen kann, ist auch in der Lage das Diffie-Hellman-Problem lösen. Solange dies nicht in vertretbarer Zeit lösbar ist kann der Angreifer den geheimen Schlüssel nicht ermitteln.

Eine Variante des Diffie-Hellman-Problems ist das \textbf{Decisional-Diffie-Hellman-Problem}. Hier muss $g^{ab}$ nicht berechnet werden, sondern lediglich entschieden werden, ob es sich bei einem gegebenen Element um $g^{ab}$ oder ein zufällig gewähltes Gruppenelement handelt. Ist dieses Problem schwierig, so hat der Angreifer, der eine Übertragung belauscht hat, keinerlei Information über den ausgetauschten Schlüssel. Dies ist eine stärkere Sicherheitseigenschaft als den Schlüssel nicht berechnen zu können.

\subsubsection{Man-In-The-Middle-Attacke}

\begin{figure}[htbp]
\centering
\fbox{\includegraphics[scale=0.5]{ex4/images/Man_in_the_middle_attack.png}}
\caption{Man in the Middle}
\label{man_in_the_middle}
\end{figure}


Beim \textbf{Man-In-The-Middle-Angriff} sitzt der Angreifer zwischen den beiden Personen, die eine geheime Nachricht übermitteln möchten. Der Angreifer tauscht mit beiden Personen einen geheimen Schlüssel aus. Diese denken, der Schlüssel käme vom jeweils Anderen. Alle Nachrichten die jetzt gesendet werden, werden vom Angreifer abgefangen, entschlüsselt, mit dem zweiten Schlüssel verschlüsselt und an die andere Person weiter gesendet.\\

\subsection{Andere Gruppen}
Das Diffie-Hellman-Verfahren ist in allen zyklischen Gruppen sicher implementierbar, solange die Gruppenoperationen darin effizient realisierbar sind und das Diffie-Hellman-Problem schwer zu lösen ist (insb. diskrete Logarithmen in $G$).

Alice und Bob einigen sich auf eine endliche zyklische Gruppe $G$ und einen Erzeuger $g$ von $G$. Sei $n$ die Ordnung von $G$. Alice wählt eine natürliche Zahl $a\in\lbrace 1, 2...,n-1\rbrace$ zufällig. Sie berechnet $A=g^a$ und schickt das Ergebnis $A$ an Bob. Er berechnet $B=g^b$ und schickt das Ergebnis zurück an Alice. Diese berechnet $B^a = g^{ab}$ und Bob $A^b = g^{ab}$. Der gemeinsame Schlüssel ist $K=g^{ab}$.